import cn.hutool.core.collection.CollectionUtil;
import cn.hutool.core.util.ArrayUtil;

import java.util.*;

/**
 * @Description: LeetCode每日练习
 * @Author: zhanglinxin
 * @CreateTime: 2025-04-01
 * @Version: 1.0
 */
public class Solution202506 {
    /**
     * @Description: 给你一个由小写英文字母组成的字符串 s 。
     * 请你找出字符串中两个字符 a1 和 a2 的出现频次之间的 最大 差值 diff = a1 - a2，这两个字符需要满足：
     * a1 在字符串中出现 奇数次 。
     * a2 在字符串中出现 偶数次 。
     * 返回 最大 差值。
     * <p>
     * 示例 1：
     * 输入：s = "aaaaabbc"
     * 输出：3
     * 解释：
     * 字符 'a' 出现 奇数次 ，次数为 5 ；字符 'b' 出现 偶数次 ，次数为 2 。
     * 最大差值为 5 - 2 = 3 。
     * <p>
     * 示例 2：
     * 输入：s = "abcabcab"
     * 输出：1
     * 解释：
     * 字符 'a' 出现 奇数次 ，次数为 3 ；字符 'c' 出现 偶数次 ，次数为 2 。
     * 最大差值为 3 - 2 = 1 。
     * @param: [java.lang.String]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/6/10 09:29
     */
    public int maxDifference(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < 26; i++) {
            if (count[i] == 0) {
                continue;
            }
            for (int j = i + 1; j < 26; j++) {
                if (count[j] == 0) {
                    continue;
                }
                if (count[i] % 2 == 1 && count[j] % 2 == 0) {
                    res = Math.max(res, count[i] - count[j]);
                }
                if (count[i] % 2 == 0 && count[j] % 2 == 1) {
                    res = Math.max(res, count[j] - count[i]);
                }
            }
        }
        return res;
    }

    /**
     * 计算字符串中出现次数为奇数的最大频次与出现次数为偶数的最小频次之差
     * 注意：如果不存在奇数次字符或偶数次字符，则对应项取0参与运算
     */
    public int maxDifference2(String s) {
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= 'a' && c <= 'z') {
                freq[c - 'a']++;
            }
        }

        int maxOdd = 0;
        int minEven = Integer.MAX_VALUE;

        for (int count : freq) {
            if (count == 0) {
                continue;
            }
            if (count % 2 != 0) {
                maxOdd = Math.max(count, maxOdd);
            } else {
                minEven = Math.min(count, minEven);
            }
        }

        // 如果 minEven 没有被更新，则说明没有偶数次出现的字符
        if (minEven == Integer.MAX_VALUE) {
            minEven = 0;
        }

        return maxOdd - minEven;
    }

    /**
     * @Description: 给你一个 循环 数组 nums ，请你找出相邻元素之间的 最大 绝对差值。
     * 注意：一个循环数组中，第一个元素和最后一个元素是相邻的。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,4]
     * 输出：3
     * 解释：
     * 由于 nums 是循环的，nums[0] 和 nums[2] 是相邻的，它们之间的绝对差值是最大值 |4 - 1| = 3 。
     * <p>
     * 示例 2:
     * 输入：nums = [-5,-10,-5]
     * 输出：5
     * 解释：
     * 相邻元素 nums[0] 和 nums[1] 之间的绝对差值为最大值 |-5 - (-10)| = 5 。
     * @param: [int[]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/6/12 15:59
     */
    public int maxAdjacentDistance(int[] nums) {
        int res = Math.abs(nums[0] - nums[nums.length - 1]);
        for (int i = 1; i < nums.length; i++) {
            res = Math.max(res, Math.abs(nums[i] - nums[i - 1]));
        }
        return res;
    }

    /**
     * @Description: 给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，
     * 每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。
     * 对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。
     * 请你返回 p 个下标对对应数值 最大差值 的 最小值 。
     * <p>
     * 示例 1：
     * 输入：nums = [10,1,2,7,1,3], p = 2
     * 输出：1
     * 解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
     * 最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。
     * <p>
     * 示例 2：
     * 输入：nums = [4,2,1,2], p = 1
     * 输出：0
     * 解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。
     * @param: [int[], int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/6/13 08:47
     */
    public int minimizeMax(int[] nums, int p) {
        if(p == 0) return 0;
        Arrays.sort(nums);
        int[] dis = new int[nums.length - 1];
        for (int i = 0; i < dis.length; i++) {
            dis[i] = nums[i + 1] - nums[i];
        }

        int l = 0, r = 0;
        for(int i:dis) {
            r = Math.max(r,i);
        }

        while(l < r) {
            int mid = (l + r) >> 1;
            if(check(dis, p, mid)) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }

        return r;

    }
    static boolean check(int[] nums,int p,int mx) {
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] <= mx) {
                cnt++;
                i++;
            }
        }

        return cnt >= p;
    }


    public static void main(String[] args) {
        Solution202506 solution202504 = new Solution202506();
        int[] nums = {10, 1, 2, 7, 1, 3};
        int i = solution202504.minimizeMax(nums, 2);
        System.out.println(i);
    }
}
